package org.example.algorithm.binarytree;

import org.example.algorithm.TreeNode;

import java.util.*;

public class SameTreeSolution {
    public static void main(String[] args) {

    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p != null && q != null) {
            return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
        return false;
    }

    public boolean isSameTree2(TreeNode p, TreeNode q) {
        Queue<TreeNode> nodeQueue1 = new LinkedList<>();
        nodeQueue1.add(p);
        Queue<TreeNode> nodeQueue2 = new LinkedList<>();
        nodeQueue2.add(q);
        while(!nodeQueue1.isEmpty() && !nodeQueue2.isEmpty()) {
            TreeNode tempNode1 = nodeQueue1.poll();
            TreeNode tempNode2 = nodeQueue2.poll();
            if (tempNode1 == null && tempNode2 == null) {
                continue;
            } else if(tempNode1 == null || tempNode2 == null) {
                return false;
            }
            if (tempNode1.val != tempNode2.val) {
                return false;
            }
            nodeQueue1.add(tempNode1.left);
            nodeQueue1.add(tempNode1.right);
            nodeQueue2.add(tempNode2.left);
            nodeQueue2.add(tempNode2.right);
        }
        return true;
    }
}
